#include <assert.h>
#include <stdio.h>
#include <string.h>

#include <algorithm>
#include <string>

using namespace std;

#define MAXL (100000 + 5)

string HexDigitToBin(char c) {
  // 0 => 0000, 1 => 0001
  int d = (isdigit(c) ? c - '0' : c - 'A' + 10);

  string ans;
  //   ans.resize(4);
  for (int i = 0; i < 4; ++i) {
    ans.push_back((d % 2) + '0');
    d /= 2;
  }
  reverse(ans.begin(), ans.end());
  return ans;
}

string HexToBin(string str) {
  // 01 => 0000,0001
  string ans;
  ans.reserve(4 * str.length());

  for (int i = 0; i < str.length(); ++i) {
    string dig = HexDigitToBin(str[i]);
    ans.append(dig);
  }
  return ans;
}

char BinDigToOct(string str) {
  // 000 => 0, 111 => 7
  assert(str.length() == 3);

  int ans = 0;
  for (int i = 0; i < 3; ++i) {
    int d = str[i] - '0';
    ans = ans * 2 + d;
  }
  assert(0 <= ans && ans <= 7);
  return ans + '0';
}

string BinToOct(string str) {
  int rem = str.length() % 3;
  if (rem) {
    str.insert(str.begin(), (3 - rem), '0');
  }
  //   printf("%s\n", )
  assert(str.length() % 3 == 0);

  string ans;
  int ans_len = str.length() / 3;
  ans.resize(ans_len);

  for (int i = 0; i < str.length(); i += 3) {
    char dig = BinDigToOct(str.substr(i, 3));
    ans[i / 3] = dig;
  }
  // Remove leading zeros.
  while (ans[0] == '0') {
    ans.erase(ans.begin());
  }
  return ans;
}

void Test() {
   string bin = HexToBin("B441E2411DC709E111C7E1E7ACB6F8CAC0BB2FC4C8BC2AE3BAAAB9165CC458E199CB89F51B135F7091A5ABB0874DF3E8CB45");
   string oct = BinToOct(bin);
   printf("bin %s\noct %s\n", bin.c_str(), oct.c_str());
}

int main() {
    // freopen("input1.txt", "r", stdin);
  int n;
  scanf("%d", &n);
  char buf[MAXL];

  while (n--) {
    scanf("%s", buf);
    string hex(buf);
    string bin = HexToBin(hex);
    string oct = BinToOct(bin);
    printf("%s\n", oct.c_str());
  }

  return 0;
}